package learn.heap;

import learn.CommUtil;

import java.util.Arrays;

/**
 * 已知一个几乎有序的数组。几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离一定不超过k，并且k相对于数组长度来说是比较小的。
 * <p>
 * 请选择一个合适的排序策略，对这个数组进行排序。
 */
public class Question1 {


    public static void main(String[] args) {
        int[] arr = {2, 4, 0, 2, 5, 8, 7, 6, 9};
        int[] old = Arrays.copyOf(arr, arr.length);
        int k = 3;
        CommUtil.printArray("原数组", arr);
        process(arr, k);
        CommUtil.printArray("排序后", arr);
        CommUtil.check(old, arr);
    }

    public static void process(int[] arr, int k) {
        int[] help = new int[k + 1];

        for (int i = 0; i <= k; i++) {
            help[i] = arr[i];
        }
        //变成小根堆
        int index = k;
        while (index >= 0) {
            heapify(help, index--, k + 1);
        }

        int ok = 0; //已排好序的
        int j = k + 1;
        while (j < arr.length) {
            ok = j - k - 1;
            arr[ok] = help[0];
            help[0] = arr[j];
            heapify(help, 0, k + 1);
            j++;
        }
        CommUtil.printArray("排序后1", arr);
        //最后排序
        CommUtil.printArray("help排序前", help);
        int rightIndex = help.length - 1;
        while (rightIndex > 0) {
            CommUtil.swap(help, 0, rightIndex--);
            heapify1(help, 0, rightIndex + 1);
        }
        CommUtil.printArray("help排序后", help);
        //copy到新数组
        for (int m = 0; m < help.length; m++) {
            arr[++ok] = help[m];
        }


    }


    /**
     * 下沉
     *
     * @param arr
     * @param index
     * @param length
     */
    public static void heapify(int[] arr, int index, int length) {
        int left = 2 * index + 1;
        while (left < length) {
            int right = left + 1;
            //左右比
            int least = (right < length && arr[right] < arr[left]) ? right : left;
            //上下比
            least = arr[index] < arr[least] ? index : least;
            //
            if (least == index) {
                break;
            }
            CommUtil.swap(arr, index, least);
            index = least;
            left = 2 * index + 1;

        }
    }

    /**
     * 下沉
     *
     * @param arr
     * @param index
     * @param length
     */
    public static void heapify1(int[] arr, int index, int length) {
        int left = 2 * index + 1;
        while (left < length) {
            int right = left + 1;
            //左右比
            int largest = (arr[left] > arr[right] || right >= length ) ? left : right;
            //上下比
            largest = arr[index] > arr[largest] ? index : largest;
            //
            if (largest == index) {
                break;
            }
            CommUtil.swap(arr, index, largest);
            index = largest;
            left = 2 * index + 1;

        }
    }

    /**
     * 上升
     *
     * @param arr
     * @param index
     */
    public static void heapInsert(int[] arr, int index) {
        int father = -1;
        while (arr[index] > arr[father = (index - 1) / 2]) {
            CommUtil.swap(arr, index, father);
            index = father;
        }
    }
}
